#include "stdafx.h"
#include "CQuickSort.h"
#include "include/tool.h"
#include <gtest/gtest.h>

template <typename T>
int quick_sort_hoare_partition(std::vector<T> *A, int low, int high) {
    T x = (*A)[high];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        while (A[j] <= x) {
            --j;
        }
        while (A[i] >= x) {
            ++i;
        }
        if (i < j) {
            std::swap((*A)[i], (*A)[j]);
        } else {
            return j+1;
        }
    }
    for (int j = low; j <= high-1; ++j) {
        if ((*A)[j] <= x) {
            ++i;
            std::swap((*A)[i], (*A)[j]);
        }
    }
    std::swap((*A)[i+1], (*A)[high]);
    return i+1;
}

template <typename T>
int quick_sort_partition(std::vector<T> *A, int low, int high) {
    T x = (*A)[high];
    int i = low - 1;
    for (int j = low; j <= high-1; ++j) {
        if ((*A)[j] <= x) {
            ++i;
            std::swap((*A)[i], (*A)[j]);
        }
    }
    std::swap((*A)[i+1], (*A)[high]);
    return i+1;
}

template <typename T>
int quick_sort_randomized_partition(std::vector<T> *A, int low, int high) {
    srand(time(NULL));
    int i = rand() % low + high;
    std::swap((*A)[i], (*A)[high]);
    return quick_sort_partition(A, low, high);
}

template <typename T>
void quick_sort(std::vector<T> *A, int low, int high) {
    if (low < high) {
        int mid = quick_sort_partition(A, low, high);
        quick_sort(A, low, mid-1);
        quick_sort(A, mid+1, high);
    }
}

template <typename T>
void hoare_quick_sort(std::vector<T> *A, int low, int high) {
    if (low < high) {
        int mid = quick_sort_hoare_partition(A, low, high);
        quick_sort(A, low, mid-1);
        quick_sort(A, mid+1, high);
    }
}

CQuickSort::CQuickSort() {
    //ctor
}

CQuickSort::~CQuickSort() {
    //dtor
}

int CQuickSort::run(void) {
    int A[] = {31, 41, 59, 26, 41, 58, 33, 78};

    std::cout << "quick sort :";
    std::vector<int> tmp2 = create_from_array(A, SIZE(A));
    print_vector(tmp2);
    quick_sort(&tmp2, 0, tmp2.size()-1);
    print_vector(tmp2);

    std::cout << "hoare quick sort :";
    std::vector<int> tmp3 = create_from_array(A, SIZE(A));
    print_vector(tmp3);
    quick_sort(&tmp3, 0, tmp3.size()-1);
    print_vector(tmp3);

    return 0;
}

TEST(CQuickSort, run)
{
	CQuickSort().run();
}